package com.zzh.tree;

import java.util.HashMap;
import java.util.Map;

public class No105_buildTree {
    public static void main(String[] args) {
        No105Solution solution = new No105Solution();
        TreeNode treeNode = solution.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        TreeNode.printTree(treeNode);
    }
}
/*
* 画张图来表示比较方便
*
* */
class No105Solution{
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen=preorder.length;
        int inLen=inorder.length;
        Map<Integer,Integer> m=new HashMap<>();//用hashmap存值和下标用于快速检索
        for (int i=0;i<inLen;i++){
            m.put(inorder[i],i);
        }
        return build(preorder,0,preLen-1,m,0,inLen-1);
    }

    private TreeNode build(int[] preorder, int preLeft, int preRight,
                           Map<Integer, Integer> m, int inLeft, int inRight) {
        if (preLeft>preRight||inLeft>inRight){
            return null;
        }
        TreeNode root;
        root=new TreeNode(preorder[preLeft]);
        int pIndex=m.get(preorder[preLeft]);
        root.left=build(preorder,
                preLeft+1,pIndex-inLeft+preLeft,//新的前序遍历下标
                m,
                inLeft,pIndex-1);//新的中序遍历下标
        root.right=build(preorder,pIndex-inLeft+preLeft+1,preRight,m,
                pIndex+1,inRight);
        return root;

    }
}
